package BackTracking;

import java.util.Arrays;

class makesquare {

    //k是分组数目，初始化为4，startIndex表示当前的火柴，curSum记录一组的火柴和，used避免取重
    public boolean backTrack(int[] nums, int startIndex, int curSum, int k, int target, boolean []used){
        //表示能找到4组
        if(k==1){
            return true;
        }
        //当前找到一组，继续找其它组
        if(curSum==target){
            return backTrack(nums,0,0,k-1,target,used);
        }
        for (int i = startIndex; i < nums.length && curSum + nums[i] <= target; i++) {//剪枝
            if(used[i]) continue;//使用过的元素就不能再使用了
            used[i] = true;//添加元素nums[i]
            if(backTrack(nums,i+1,curSum+nums[i], k,target,used))
                return true;//如果添加这个元素后，完成了题目要求，就return true.
            used[i] = false;//回溯
            while(i<nums.length - 1&&nums[i+1]==nums[i])//剪枝3 ,非常重要，大幅提升效率
                i++; //如果某个元素无法使得组合达到目标值，那么跟它值相同的元素也不需要添加了
        }
        return false;
    }


    //你要用 所有的火柴棍 拼成一个正方形。不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次
    public boolean makesquare(int[] nums) {
        int sum = 0;
        boolean []used = new boolean[nums.length];
        Arrays.sort(nums);
        for(int n : nums) sum += n;
        if(sum % 4 != 0) return false;
        int target =  sum / 4;//target为每个子集的和
        if(nums[nums.length - 1] > target) return false;
        return backTrack(nums, 0, 0, 4, target, used);
    }
}
